Алгоритмічні основи криптології 1 рівень Означення найбільшого спільного дільника. Число d Z, що ділиться одночасно на числа а, b, c, ... , k Z, називається спільним дільником цих чисел. Найбільше d з такою властивістю називається найбільшим спільним дільником. Позначення: d = (a, b, c, ..., k). Перелічимо, подекуди доводячи, основні властивості найбільшого спільного дільника. Які числа називаються взаємно простими. Цілі числа a і b називаються взаємно простими, якщо НСД( a , b ) = 1. Означення ланцюгового дробу. Ланцюговий (чи неперервним ) дробом називається вираз виду: EMBED Equation.3
 Домовимося називати числа q 1 , q 2 ,..., q n ,... - неповними частками і вважаємо, що q 1 Z, а q 2 ,..., q n ,... N . Числа 1 = q 1 , 2 = q 1 +EMBED Equation.3
, 3 = q 1 +EMBED Equation.3
, і т.д. називаються прямуючими дробами ланцюгового дробу . Алгоритм Евкліда. Алгоритм, що дозволяє за заданими натуральними числами a і b знаходити їхній найбільший спільний дільник, вважається придумав самий впливовий математик усіх часів і народів - Евклід, він викладений у IX книзі його знаменитих "Початків". Означення простого числа. Число р N , р 1, називається простим, якщо р має лише два додатних дільники: 1 і р. Коли алгоритм Евкліда працює найдовше? Теорема (Ламе, 1845 р.). Нехай n N , і нехай a>b>0 такі, що алгоритму Евкліда для обробки а і b необхідно виконати точно n кроків (розподілів із залишком), причому а - найменше з такою властивістю. Тоді а=n +2 , b =n +1 , де k - k- те число Фібоначчі. Ну от, використовуючи теорему Ламе, ми провели деякий аналіз швидкодії алгоритму Евкліда і довідалися найгірший випадок для нього - два послідовних числа Фібоначчі. Означення числа порівняльного за модулем. Нехай а, b Z , m N. Число а порівняльне з b за модулем m, якщо а і b при діленні на m мають однакові залишки: a b(mod m) . Означення числа порівняльного за модулем. Нехай а, b Z , m N. Число а порівняльне з b за модулем m, якщо а і b при діленні на m мають однакові залишки: a b(mod m) . Означення повної системи лишків. Сукупність лишків, узятих по одному з кожного класу еквівалентності m, називається повною системою лишків за модулем m (у повній системі лишків усього m чисел). Безпосередньо самі залишки ділення на m називаються найменшими невід’ємними лишками і утворюють повну систему лишків за модулем m. Означення зведеної системи лишків. Зведеною системою лишків за модулем m називається сукупність усіх лишків з повної системи, взаємно простих з модулем m. Що означає розв’язати порівняння? Розв’язати порівняння – означає знайти всі ті х, що задовольняють даному порівнянню, при цьому весь клас чисел за mod m вважається одним розв’язком. Скільки розв’язків має порівняння за простим модулем p? Довільне нетривіальне порівняння за mod p рівносильне порівнянню степеня не вищого за p-1 і має не більше p-1 розв’язків. Які порівняння називаються рівносильними? Порівняння називаються рівносильними, якщо вони мають однакові розв’язки – повна аналогія з поняттям рівносильності рівнянь. Наведіть функцію знаходження кількості дільників даного числа. Наведіть функцію знаходження суми дільників даного числа. Означення алгоритму. Слово "алгоритм" є російською транскрипцією латинізованого імені видатного арабського математика ал-Хорезми Абу Абдули Мухаммеда ібн ал-Маджусі (787 - 850) і означає в сучасному смислі деякі правила, список інструкцій чи команд, виконуючи які, хтось досягне необхідного результату. Чи можна розкласти довільне ціле число відмінне від -1, 0, 1 за допомогою добутку простих чисел? Усяке ціле число, відмінне від -1, 0 і 1, єдиним чином (з точністю до порядку співмножників) розкладається за допомогою добутку простих чисел. 2 рівень Типи задач в теорії алгоритмів. Наведіть характеристики. Діофантові рівняння. Частковий та повний розв’язок. Звичайно, довільне рівняння (але, як правило, усе-таки з цілими коефіцієнтами) одержує титул "діофантове"...